package com.mj.listen2._01_排序.cmp;

/**
 * 插入排序
 *
 * @param <T>
 */
public class _04_InsertSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
//        insertSort1();
//        insertSort2();
//        insertSort3();
//        insertSort4();
        insertSort5();
    }

    /**
     * 插入排序
     */
    private void insertSort1() {
        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (cmp(j, j + 1) > 0) {
                    swap(j, j + 1);
                }
            }
        }
    }

    /**
     * 插入排序的优化，不交换，只顺移
     */
    private void insertSort2() {
        int index = 0;
        for (int begin = 1; begin < array.length; begin++) {
            // 取出 begin 位置的值
            T temp = array[begin];
            for (int i = begin - 1; i >= 0; i--) {
                // 拿着temp依次与前面已经排好序的元素进行比较
                if (cmp(array[i], temp) > 0) {// 前面的数据大
                    // 前面的数据依次往后顺移
                    array[i + 1] = array[i];
                } else {
                    // 第一次找到比temp小的或者相等的值，记录这次的index
                    index = i;
                    // 插入到找到的索引的后边
                    array[index + 1] = temp;
                    break;
                }
            }
        }
    }

    // 相比较 insertSort2() 可以省略写 index
    private void insertSort3() {
        for (int begin = 1; begin < array.length; begin++) {
            // 取出 begin 位置的值
            T temp = array[begin];
            for (int i = begin - 1; i >= 0; i--) {
                // 拿着temp依次与前面已经排好序的元素进行比较
                if (cmp(array[i], temp) > 0) {// 前面的数据大
                    // 前面的数据依次往后顺移
                    array[i + 1] = array[i];
                } else {
                    // 插入到找到的索引的后边
                    array[i + 1] = temp;
                    break;
                }
            }
        }
    }

    /**
     * while循环的方式
     */
    private void insertSort4() {
        for (int begin = 1; begin < array.length; begin++) {
            int curIndex = begin;
            while (curIndex > 0 && cmp(curIndex, curIndex - 1) < 0) {
                swap(curIndex, curIndex - 1);
                curIndex--;
            }
        }
    }

    /**
     * while循环的优化，不交换，只顺移
     */
    private void insertSort5() {
        for (int begin = 1; begin < array.length; begin++) {
            int curIndex = begin;
            T temp = array[curIndex];
            while (curIndex > 0 && cmp(temp, array[curIndex - 1]) < 0) {
                // 前面的值大
                array[curIndex] = array[curIndex - 1];
                curIndex--;
            }
            array[curIndex] = temp;
        }
    }
}
